
def knapsack(n: int, c: int, w: list[int], v: list[int]) -> int:
    dp = [0] * (c + 1)
    for i in range(0, n):
        for j in range(c, w[i] - 1, -1):
            dp[j] = max(dp[j], v[i] + dp[j - w[i]])
    return dp[-1]
